home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / ddj0290.arc / STEVENS.LST < prev    next >
File List  |  1990-01-07  |  18KB  |  621 lines
  1. _C PROGRAMMING COLUMN_
  2. by Al Stevens
  3.  
  4. [LISTING ONE]
  5.  
  6. /* ----------- textsrch.h ---------- */
  7.  
  8. #define OK    0
  9. #define ERROR !OK
  10.  
  11. #define MXTOKS 25           /* maximum number of tokens */
  12. #define MAXFILES 64         /* maximum number of files  */
  13. #define MAXWORDLEN 25       /* maximum word length      */
  14. #define MAPSIZE MAXFILES/16 /* number of ints/map       */
  15.  
  16. #define SLOTINDEX  "slots.ndx"
  17. #define TEXTINDEX  "text.ndx"
  18. #define FILELIST   "filelist.ndx"
  19.  
  20. /* ---- the search decision bitmap (one bit per file) ---- */
  21. struct bitmap {
  22.     int map[MAPSIZE];
  23. };
  24.  
  25. /* ------- the postfix expression structure -------- */
  26. struct postfix  {
  27.     char pfix;      /* tokens in postfix notation */
  28.     char *pfixop;   /* operand strings            */
  29. };
  30.  
  31. /* --------- the postfix stack ---------- */
  32. extern struct postfix pftokens[];
  33. extern int xp_offset;
  34.  
  35. /* --------- expression token values ---------- */
  36. #define TERM     0
  37. #define OPERAND 'O'
  38. #define AND     '&'
  39. #define OR      '|'
  40. #define OPEN    '('
  41. #define CLOSE   ')'
  42. #define NOT     '!'
  43. #define QUOTE   '"'
  44.  
  45. /* --------------- textsrch prototypes --------------- */
  46. struct postfix *lexical_scan(char *expr);
  47. struct bitmap exinterp(void);
  48. struct bitmap search(char *word);
  49. void process_result(struct bitmap);
  50.  
  51. /* -------------- binary tree prototypes ------------- */
  52. void addtree(char *s);
  53. int srchtree(char *s);
  54. void delete_tree(void);
  55. void build_noisewords(void);
  56.  
  57. /* ------------- command line prototypes ------------- */
  58. void parse_cmdline(int,char **,char *,void (*)(char *));
  59.  
  60. /* ---------------- text prototypes ------------------ */
  61. void extract_word(FILE *fp, char *s);
  62.  
  63. /* --------------- index prototypes ------------------ */
  64. void open_database(void);
  65. void init_database(void);
  66. void close_database(void);
  67. void addindex(char *word, int fileno);
  68. void indexing(char *filename);
  69. int getbit(struct bitmap *map1, int bit);
  70. struct bitmap search_index(char *word);
  71. char *text_filename(int fileno);
  72.  
  73.  
  74.  
  75. [LISTING TWO]
  76.  
  77. /* ----------- cmdline.c ----------- */
  78.  
  79. #include <stdio.h>
  80. #include <dir.h>
  81. #include <string.h>
  82. #include "textsrch.h"
  83.  
  84. /*
  85.  * Parse a command line:
  86.  *  filename1 filename2 ... filenamen
  87.  *  @filelist
  88.  *  wild cards
  89.  *  -+x option list (-a +b -c -xyz +pdq)
  90.  *  any mix of the above
  91.  */
  92.  
  93. /* ---- parse a command line for options and file names ---- */
  94. void parse_cmdline(int argc, char *argv[], char *options,
  95.                 void (*func)(char *fn))
  96. {
  97.     char path[65];
  98.     FILE *fp;
  99.     while (argc-- > 1)  {
  100.         switch (**++argv)   {
  101.             case '/':
  102.             case '+':
  103.                 /* -------- add an option --------- */
  104.                 while (options && *++*argv)
  105.                     options[**argv] = 1;
  106.                 break;
  107.             case '-':
  108.                 /* -------- remove an option --------- */
  109.                 while (options && *++*argv)
  110.                     options[**argv] = 0;
  111.                 break;
  112.             case '@':
  113.                 /* ----- a file of file path/names ----- */
  114.                 if ((fp = fopen(*argv+1, "rt")) != NULL)
  115.                     while ((fgets(path, 65, fp)) != NULL)   {
  116.                         path[strlen(path)-1] = '\0';
  117.                         (*func)(path);
  118.                     }
  119.                 break;
  120.             default:
  121.                 /* ---- a file spec on the command line ---- */
  122.                 if (strchr(*argv, '*') || strchr(*argv, '?')) {
  123.                     /* ------ an ambiguous file spec ------- */
  124.                     struct ffblk ff;
  125.                     char *cp;
  126.                     int rtn;
  127.  
  128.                     /* ---- copy the ambiguous file spec ---- */
  129.                     strcpy(path, *argv);
  130.  
  131.                     /* ---- find the filename part ---- */
  132.                     if ((cp = strrchr(path, '\\')) == NULL)
  133.                         if ((cp = strrchr(path, ':')) == NULL)
  134.                             cp = path-1;
  135.                     cp++;
  136.  
  137.                     /* ---- search for matches ---- */
  138.                     rtn = findfirst(*argv, &ff, 0);
  139.                     while (rtn == 0)    {
  140.                         strcpy(cp, ff.ff_name);
  141.                         (*func)(path);
  142.                         rtn = findnext(&ff);
  143.                     }
  144.                 }
  145.                 else
  146.                     /* ----- an unambiguous file spec ----- */
  147.                     (*func)(*argv);
  148.                 break;
  149.         }
  150.     }
  151. }
  152.  
  153.  
  154.  
  155. [LISTING THREE]
  156.  
  157. /* ------------ bintree.c ---------- */
  158.  
  159. #include <stdio.h>
  160. #include <string.h>
  161. #include <stdlib.h>
  162. #include "textsrch.h"
  163.  
  164. struct bintree {
  165.     struct bintree *lower;
  166.     struct bintree *higher;
  167.     char wd[1];
  168. };
  169.  
  170. static struct bintree *first, *next;
  171.  
  172. /* ---------- add a string to a binary tree ----------- */
  173. void addtree(char *s)
  174. {
  175.     struct bintree *tp;
  176.     int intree;
  177.  
  178.     tp = malloc(sizeof (struct bintree) + strlen(s));
  179.     if (tp == NULL)
  180.         return;
  181.     strcpy(tp->wd, s);
  182.     tp->lower = tp->higher = NULL;
  183.     if ((intree = srchtree(s)) != 0)    {
  184.         if (first == NULL)
  185.             first = tp;
  186.         if (next != NULL)   {
  187.             if (intree < 0)
  188.                 next->lower = tp;
  189.             else
  190.                 next->higher = tp;
  191.         }
  192.     }
  193. }
  194.  
  195. /* ------ Search a binary tree for a string.
  196.     Return 0 if the string is in the tree.
  197.     Return < 0 or > 0 if not.
  198.     If not, next -> the node where insertion may occur. --- */
  199.  
  200. int srchtree(char *s)
  201. {
  202.     struct bintree *this;
  203.     int an = -1;
  204.     this = next = first;
  205.     while (this != NULL)    {
  206.         if ((an = strcmp(s, this->wd)) == 0)
  207.             break;
  208.         next = this;
  209.         this = ((an < 0) ? this->lower : this->higher);
  210.     }
  211.     return an;
  212. }
  213.  
  214. /* ------- delete the nodes of a branch of the tree ------ */
  215. static void delete_nodes(struct bintree *nd)
  216. {
  217.     if (nd->lower)
  218.         delete_nodes(nd->lower);
  219.     if (nd->higher)
  220.         delete_nodes(nd->higher);
  221.     free(nd);
  222. }
  223.  
  224. /* ------- free all memory allocated for the tree -------- */
  225. void delete_tree(void)
  226. {
  227.     delete_nodes(first);
  228. }
  229.  
  230. /* ------- build a binary tree of noise words -------- */
  231. void build_noisewords(void)
  232. {
  233.     FILE *fp;
  234.     char word[MAXWORDLEN+1];
  235.     /* ---- open the noise word file ---- */
  236.     if ((fp = fopen("NOISE.LST", "rt")) != NULL)    {
  237.     /* ---- extract words and add them to the list ---- */
  238.         while (!feof(fp))   {
  239.             extract_word(fp, word);
  240.             /* -------- search the noise word list -------- */
  241.             addtree(word);
  242.         }
  243.         fclose(fp);
  244.     }
  245. }
  246.  
  247.  
  248.  
  249. [LISTING FOUR]
  250.  
  251. so very what he she her both there if above only it again
  252. done our then from just my along left who may we all these
  253. them us after once need through onto others can want where
  254. would nor none with do here been was see own since off this
  255. not will which itself that each to take down on you under at
  256. their however the an as even have whose a said before or
  257. nearly below are those possible alike begin out than having
  258. two know when way often together by many thus whatever i his
  259. past another though other entire in against am most taken
  260. instead him because for might too rather few soon either near
  261. about every until neither beyond your better must usually
  262. several does such something using put more whether sent any
  263. later like and now they also upon close be use of is should
  264. could were into made further used let how enough its himself
  265. known never become sure over next up among had causes has no
  266. old some come but while me
  267.  
  268.  
  269.  
  270. [LISTING FIVE]
  271.  
  272. /* ----------- index.c ------------- */
  273.  
  274. #include <stdio.h>
  275. #include <stdlib.h>
  276. #include <string.h>
  277. #include "textsrch.h"
  278.  
  279. static void setbit(struct bitmap *map1, int bit);
  280. static unsigned compute_hash(char *word);
  281.  
  282. static FILE *slots, *text, *flist;
  283. static char path[65];
  284. int file_count = 0;
  285.  
  286. /* ------ open or create the index files for building ------ */
  287. void open_database(void)
  288. {
  289.     unsigned ctr = 0xffff;
  290.     long empty = -1L;
  291.     build_noisewords();
  292.     if ((slots = fopen(SLOTINDEX, "r+b")) == NULL)
  293.         slots = fopen(SLOTINDEX, "w+b");
  294.     if (slots != NULL)  {
  295.         if ((text = fopen(TEXTINDEX, "r+b")) == NULL)
  296.             text = fopen(TEXTINDEX, "w+b");
  297.         if (text != NULL)   {
  298.             if ((flist = fopen(FILELIST, "rt")) != NULL)    {
  299.                 while (fread(path, sizeof path, 1, flist))
  300.                     file_count++;
  301.                 fclose(flist);
  302.                 flist = fopen(FILELIST, "at");
  303.                 return;
  304.             }
  305.             /* ---- if the file list does not exist,
  306.                 we must be building a new data base ----- */
  307.             if ((flist = fopen(FILELIST, "wt")) != NULL) {
  308.                 /* --- preset the slots to -1 values --- */
  309.                 printf("\nBuilding index. Please wait...\n");
  310.                 while (ctr--)   {
  311.                     if ((ctr % 1000) == 0)
  312.                         putchar('.');
  313.                     fwrite(&empty, sizeof(long), 1, slots);
  314.                 }
  315.                 file_count = 0;
  316.                 return;
  317.             }
  318.             fclose(text);
  319.         }
  320.         fclose(slots);
  321.     }
  322.     printf("\nCannot establish index files");
  323.     exit(1);
  324. }
  325.  
  326. /* -------- open an index data base for retrieval ------- */
  327. void init_database(void)
  328. {
  329.     build_noisewords();
  330.     /* ---------- open all three index files ---------- */
  331.     if ((slots = fopen(SLOTINDEX, "rb")) != NULL)   {
  332.         if ((text = fopen(TEXTINDEX, "rb")) != NULL)    {
  333.             if ((flist = fopen(FILELIST, "rt")) != NULL) {
  334.                 /* ------- count the text files ---------- */
  335.                 while (fread(path, sizeof path, 1, flist))
  336.                     file_count++;
  337.                 printf("\n%d files in the data base.",
  338.                             file_count);
  339.                 return;
  340.             }
  341.             fclose(text);
  342.         }
  343.         fclose(slots);
  344.     }
  345.     printf("\nCannot open Index Data Base");
  346.     exit(1);
  347. }
  348.  
  349. /* --------- close the index files ---------- */
  350. void close_database(void)
  351. {
  352.     delete_tree();
  353.     fclose(slots);
  354.     fclose(text);
  355.     fclose(flist);
  356. }
  357.  
  358. /* --------- add a word to the index
  359.         or add the file number to the existing word -------- */
  360. void addindex(char *word, int fileno)
  361. {
  362.     long slotno;
  363.     long hash;
  364.     struct bitmap map1;
  365.     long ptr = -1L;
  366.     char wd[MAXWORDLEN+1];
  367.  
  368.     /* ------- compute a randon address from the word ------ */
  369.     hash = compute_hash(word);
  370.     hash *= sizeof(long);
  371.     /* ------ read the random slot value -------- */
  372.     fseek(slots, hash, SEEK_SET);
  373.     fread(&slotno, sizeof(long), 1, slots);
  374.     if (slotno == -1L)  {
  375.         /* --- empty slot, add the word to the data base --- */
  376.         fseek(text, 0L, SEEK_END);
  377.         slotno = ftell(text);
  378.         /* ----- set the bit map to this file only ----- */
  379.         memset(&map1, 0, sizeof(struct bitmap));
  380.         setbit(&map1, fileno);
  381.         fwrite(&map1, sizeof(struct bitmap), 1, text);
  382.         /* -- set the chain pointer to the terminal value -- */
  383.         fwrite(&ptr, sizeof(long), 1, text);
  384.         fwrite(word, strlen(word)+1, 1, text);
  385.         /* --- insert the text address into the slot file --- */
  386.         fseek(slots, hash, SEEK_SET);
  387.         fwrite(&slotno, sizeof(long), 1, slots);
  388.         return;
  389.     }
  390.     /* -------- the hashed slot is in use -------- */
  391.     for (;;)    {
  392.         /* --- point to the text index record ---- */
  393.         fseek(text, slotno, SEEK_SET);
  394.         fread(&map1, sizeof(struct bitmap), 1, text);
  395.         fread(&ptr, sizeof(long), 1, text);
  396.         fgets(wd, MAXWORDLEN+1, text);
  397.         /* --- see if the entry matches the word --- */
  398.         if (strcmp(wd, word) == 0)  {
  399.             /* ---- the word matches this entry,
  400.                     set this file's bit ---- */
  401.             setbit(&map1, fileno);
  402.             fseek(text, slotno, SEEK_SET);
  403.             fwrite(&map1, sizeof(struct bitmap), 1, text);
  404.             break;
  405.         }
  406.         /* ----- see if there is a chain ----- */
  407.         if (ptr == -1)  {
  408.             /* ------ end of the chain; add this word ---- */
  409.             long newslotno;
  410.             /* ---- to the end of the text index file ---- */
  411.             fseek(text, 0L, SEEK_END);
  412.             newslotno = ftell(text);
  413.             /* ----- set the bit map to this file only ----- */
  414.             memset(&map1, 0, sizeof(struct bitmap));
  415.             setbit(&map1, fileno);
  416.             fwrite(&map1, sizeof(struct bitmap), 1, text);
  417.             fwrite(&ptr, sizeof(long), 1, text);
  418.             fwrite(word, strlen(word)+1, 1, text);
  419.             /* ----- chain the last entry to this one ----- */
  420.             fseek(text, slotno+sizeof(struct bitmap), SEEK_SET);
  421.             fwrite(&newslotno, sizeof(long), 1, text);
  422.             break;
  423.         }
  424.         /* ------ the text record is chained
  425.             (multiple words hash to the same slot) ---- */
  426.         slotno = ptr;
  427.     }
  428. }
  429.  
  430. /* ------ search the data base for a match on a word ------ */
  431. struct bitmap search_index(char *word)
  432. {
  433.     long slotno = -1;
  434.     long hash;
  435.     struct bitmap map1;
  436.     char wd[MAXWORDLEN+1];
  437.  
  438.     /* ----- preset the bit map to all zeros ----- */
  439.     memset(&map1, 0, sizeof(struct bitmap));
  440.     /* ---- compute random slot address for the word ---- */
  441.     hash = compute_hash(word);
  442.     hash *= sizeof(long);
  443.     fseek(slots, hash, SEEK_SET);
  444.     fread(&slotno, sizeof(long), 1, slots);
  445.     /* ------- navigate the chain -------- */
  446.     while (slotno != -1)    {
  447.         fseek(text, slotno, SEEK_SET);
  448.         fread(&map1, sizeof(struct bitmap), 1, text);
  449.         fread(&slotno, sizeof(long), 1, text);
  450.         fgets(wd, MAXWORDLEN+1, text);
  451.         if (strcmp(wd, word) == 0)
  452.             /* ---- the word matches this entry ---- */
  453.             break;
  454.         memset(&map1, 0, sizeof(struct bitmap));
  455.     }
  456.     return map1;
  457. }
  458.  
  459. /* ---- compute a random address from an ASCII string ---- */
  460. static unsigned compute_hash(char *word)
  461. {
  462.     unsigned hash = 0;
  463.     while (*word)
  464.         hash = (hash << 7) + (hash >> 9) + *word++;
  465.     return hash;
  466. }
  467.  
  468. /* ------ sets a designated bit in the bit map ------ */
  469. static void setbit(struct bitmap *map1, int bit)
  470. {
  471.     int off = bit / 16;
  472.     int mask = 1 << (bit % 16);
  473.     map1->map[off] |= mask;
  474. }
  475.  
  476. /* ------ tests a designated bit in the bit map ------ */
  477. int getbit(struct bitmap *map1, int bit)
  478. {
  479.     int off = bit / 16;
  480.     int mask = 1 << (bit % 16);
  481.     return map1->map[off] & mask;
  482. }
  483.  
  484. /* --------- add a file name to the list ----------- */
  485. void indexing(char *filename)
  486. {
  487.     /* ----- add the file path to the index file list ------ */
  488.     memset(path, '\0', sizeof path);
  489.     strcpy(path, filename);
  490.     fwrite(path, sizeof path, 1, flist);
  491.     file_count++;
  492. }
  493.  
  494. /* ---- return the file name associated with an offset ---- */
  495. char *text_filename(int fileno)
  496. {
  497.     fseek(flist, (long) (fileno * sizeof path), SEEK_SET);
  498.     fread(path, sizeof path, 1, flist);
  499.     return path;
  500. }
  501.  
  502. [LISTING SIX]
  503.  
  504. /* -------------- bldindex.c --------------- */
  505.  
  506. #include <stdio.h>
  507. #include <string.h>
  508. #include "textsrch.h"
  509.  
  510. static void index_file(char *filename);
  511.  
  512. void main(int argc, char *argv[])
  513. {
  514.     open_database();
  515.     printf("\nTextSrch: Building a TextSrch Index File");
  516.     parse_cmdline(argc, argv, NULL, index_file);
  517.     close_database();
  518. }
  519.  
  520. static void index_file(char *filename)
  521. {
  522.     FILE *fp;
  523.     char word[MAXWORDLEN+1];
  524.     extern int file_count;
  525.     int wdctr = 0;
  526.  
  527.     printf("\nIndexing %s", filename);
  528.     indexing(filename);
  529.     /* ---- open the object file ---- */
  530.     if ((fp = fopen(filename, "rt")) == NULL)   {
  531.         printf("\nError: No such file");
  532.         return;
  533.     }
  534.     putchar('\n');
  535.     /* ---- extract words and add them to the index ---- */
  536.     while (!feof(fp))   {
  537.         extract_word(fp, word);
  538.         /* -------- search the noise word list -------- */
  539.         if (srchtree(word) != 0)    {
  540.             if ((++wdctr % 100) == 0)
  541.                 printf("\r%5d words", wdctr);
  542.             /* ------- add the word to the index ------- */
  543.             addindex(word, file_count-1);
  544.         }
  545.     }
  546.     printf("\r%5d words", wdctr);
  547.     fclose(fp);
  548. }
  549.  
  550.  
  551.  
  552.  
  553.  
  554. [LISTING SEVEN]
  555.  
  556. /* ----------- text.c ------------ */
  557.  
  558. #include <stdio.h>
  559. #include <ctype.h>
  560. #include "textsrch.h"
  561.  
  562. #define isTEXT(c) (isalpha(c) || isdigit(c) || \
  563.                    c=='+' || c=='#' || c=='_')
  564.  
  565. /* --------- extract a word from an input stream ----------- */
  566. void extract_word(FILE *fp, char *s)
  567. {
  568.     int i, c;
  569.  
  570.     c = i = 0;
  571.     while (!isTEXT(c))
  572.         if ((c = fgetc(fp)) == EOF)
  573.             break;
  574.     while (isTEXT(c))   {
  575.         if  (i++ < MAXWORDLEN)
  576.             *s++ = tolower(c);
  577.         if ((c = fgetc(fp)) == EOF)
  578.             break;
  579.     }
  580.     *s = '\0';
  581. }
  582.  
  583.  
  584.  
  585.  
  586. [LISTING EIGHT]
  587.  
  588. /* ---------- search.c ----------- */
  589.  
  590. /*
  591.  * the TEXTSRCH retrieval process
  592.  */
  593.  
  594. #include <stdio.h>
  595. #include <string.h>
  596. #include "textsrch.h"
  597.  
  598. /* ---- process the result of a query expression search ---- */
  599. void process_result(struct bitmap map1)
  600. {
  601.     int i;
  602.     extern int file_count;
  603.     for (i = 0; i < file_count; i++)
  604.         if (getbit(&map1, i))
  605.             printf("\n%s", text_filename(i));
  606. }
  607.  
  608. /* ------- search the data base for a word match -------- */
  609. struct bitmap search(char *word)
  610. {
  611.     struct bitmap map1;
  612.  
  613.     memset(&map1, 0xff, sizeof (struct bitmap));
  614.     if (srchtree(word) != 0)
  615.         map1 = search_index(word);
  616.     return map1;
  617. }
  618.  
  619.  
  620.  
  621.